from LeetCoder import *


class Solution:

    def doesValidArrayExist(self, derived: List[int]) -> bool:
        if len(derived) == 1:
            return derived[0] == 0
        a = derived[0]

        def f(i, j):
            ans = [0] * len(derived)
            ans[0] = i
            ans[1] = j
            for k in range(2, len(derived)):
                a, b = derived[k - 2], derived[k - 1]
                if a == b:
                    ans[k] = ans[k - 2]
                else:
                    ans[k] = ans[k - 2] ^ 1
            return derived[-1] == ans[0] ^ ans[-1]

        if a == 1:
            return f(1, 0) or f(0, 1)
        return f(0, 0) or f(1, 1)





s = Solution()
print(s.doesValidArrayExist(derived=[0, 0, 1]))
print(s.doesValidArrayExist(derived=[1, 1, 0]))
print(s.doesValidArrayExist(derived=[1, 1]))
print(s.doesValidArrayExist(derived=[1, 0]))
